1. Field of Invention
The present invention relates generally to scheduling complex jobs, and particularly to a scheduling system and process that minimizes the cost of job completion.
2. Description of the Related Art
There is a wide variety of complex projects that take place throughout the modern global marketplace. Because of the sheer size of these projects, substantial planning and organization is required. For example, one does not just build a building. Rather, one starts with a design, drafts blueprints, and works in stages up to the finished project, overcoming hundreds of hurdles along the way. In terms of the actual construction itself, even this must be well planned ahead of time. For example, certain aspects of a construction project cannot be completed out of sequence. When constructing a ship, one cannot paint the ship until the hull is built. An elevator cannot be installed in a building until there is an elevator shaft. These are two simple examples, but it is easy to understand how there could be hundreds or thousands of constraints such as these in any large project involving construction. Furthermore, we can generalize this problem beyond the construction space. In fact, any large project, whether it be construction, manufacturing, or even the execution of a computer program, that has certain constraints on the utilization of resources, has a need for an efficient allocation of those resources according to some well planned schedule, in order to control the cost of the project.
A variety of automated scheduling techniques has been developed in recent years. These techniques often work by reducing scheduling problems to “Constraint-Satisfaction Problems” (CSPs) and then applying one of a variety of CSP techniques to solving them. See, for example, U.S. Pat. No. 6,070,144, “System and Process for Job Scheduling Using Limited Discrepancy Search,” to Ginsberg et al., which is herein incorporated by reference in its entirety; and articles by Stephen Smith, Senior Research Scientist, ICL Laboratory, which may be found at http://www.ri.cmu.edu/people/smith_stephen.html. Virtually all of these techniques have been designed to minimize the “makespan” of the schedule in question, i.e., the time taken to complete the job in its entirety. In some cases, an attempt is made to level the resources utilized while the job is in process, for instance as is done by the “Resource Leveling” tool in Microsoft's Project software, but typically the “load leveling” technology is just a misnomer for a search algorithm that minimizes makespan. For example, the load leveling option in Artemis, a commercial scheduler by Artemis Management Systems of Boulder, Colo., requires that the user specify predetermined resource limits. If no schedule can be found that honors these user-specified limits, the deadline of the schedule is slipped as necessary.
In practice, minimizing schedule makespan is often a stand-in for the true optimization goal of minimizing the total cost of resources used during construction. Consider, for example, the cost of labor. This cost is a function of the actual labor cost of the tasks in the schedule itself, which can be represented as La, together with the costs involved in having workers sit idle while waiting for something to do, or hiring and/or firing workers who are no longer needed to complete a project, which can be symbolized as Li. The overall cost of project completion, L, is typically a combination of the actual working costs and the “indirect” costs associated with hiring and layoffs, idle workers and overtime, i.e. L=La+Li.
It has generally been felt that since shorter schedules involve fewer gaps where workers are idle, i.e. lower values of Li, makespan minimization leads to the least expensive schedules. However, even with makespan minimization, there can still be a large amount of inefficiency in the resulting schedules, leading to waste and unnecessary cost. For example, an overly short schedule might incur extra costs to hire the workers needed to complete the task in such a short time, or more generally, it might cause (or fail to prevent) unnecessary variation in the work effort. Even lowering the maximum resource usage does not necessarily minimize the costs associated with the variation in resource usage. For example, suppose the maximum resource usage for a particular resource were lowered to 20 people. The schedule might have 20 people on one day, and two people on the next day, thus incurring substantial inefficiency.
Even small inefficiencies can mean substantially higher costs. A one percent cost increase in the building of a $500 million nuclear submarine is $5 million—hardly negligible.
Therefore, what is needed is a system and method for producing a workflow schedule that results in increased efficiency—and thus financial savings—compared to present systems, including those using simple makespan minimization schedules.